#include<iostream>
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* last;
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr) return head;
        int step = 1;
        int len = 1;
        ListNode* pro = head;
        
        while (pro != nullptr) {
            pro = pro->next;
            len++;
        }
        ListNode* l1, *l2,* r1,* r2;
        int nowstep = 0;
        ListNode* now;
        ListNode* trueHead = head;
        for (step = 1; step < len; step <<= 1) {
            bool isFirst = true;
            now = trueHead;
            while (now != nullptr) {
                l1 = now;
                bool flag = true;
                nowstep = 1;
                while (nowstep < step) {
                    if (now == nullptr) {
                        flag = false;
                        break;
                    }
                    nowstep++;
                    now = now->next;
                }
                if (flag == false||now==nullptr||now->next==nullptr) break;
                l2 = now;
              //  std::cout << l1->val << " " << l2->val << std::endl;
                r1 = now->next;
                now = now->next;
               // std::cout << now->val << "nn\n";
                nowstep = 1;
                while (now != nullptr&& now->next!= nullptr && nowstep < step) {
                    nowstep++;
                    now = now->next;
                  //  std::cout << now->val << "nn\n";
                }
                r2 = now;
                now = now->next;
             //   std::cout << l1->val << "true" << l2->val << std::endl;
             //  std::cout << r1->val << "true" << r2->val << std::endl;
             //   std::cout << step << "true" << std::endl;
                if (isFirst) {
                    trueHead = firstMerge(l1, l2, r1, r2);
                    isFirst = false;
                }
                else {
                    nextMerge(l1, l2, r1, r2);
                }
            }
            }
           
        return trueHead;
    }
    void nextMerge(ListNode* l1, ListNode* l2, ListNode* r1, ListNode* r2) {
        ListNode* end = r2->next;
        ListNode* left = l1;
        ListNode* right = r1;
        ListNode* prel = nullptr;
        ListNode* prer = nullptr;
        ListNode* now = last;

        while (prel != l2 && prer != r2) {
            if (left->val < right->val) {
                now->next = left;
                now = left;
                prel = left;
                left = left->next;
            }
            else {
                now->next = right;
                now = right;
                prer = right;
                right = right->next;
            }
        }

        if (prel != l2) {
            now->next = left;
            l2->next = end;
            last = l2;
        }
        if (prer != r2) {
            now->next = right;
            r2->next = end;
            last = r2;
        }

    }
    ListNode* firstMerge(ListNode* l1, ListNode* l2, ListNode* r1, ListNode* r2) {
        ListNode* end = r2->next;
        ListNode* left = l1;
        ListNode* right = r1;
        ListNode* prel = nullptr;
        ListNode* prer = nullptr;
        ListNode* head;
        ListNode* now = new ListNode(1);
        head = now;

        while (prel != l2 && prer != r2) {
            if (left->val < right->val) {
                now->next = left;
                now = left;
                prel = left;
                left = left->next;
            }
            else {
                now->next = right;
                now = right;
                prer = right;
                right = right->next;
            }
        }

        if (prel != l2) {
            now->next = left;
            l2->next = end;
            last = l2;
        }
       if (prer != r2) {
            now->next = right;
            r2->next = end;
            last = r2;
        }
    
      
        return head->next;
    }

   

};

